package com.bclz.al.linlist

import com.bclz.al.dynamic.List

class LinkedListViaDouble[T]() extends List[T] {

  //not use case  class,默认tostring会stackover
   class Node[T](var ele:T,var next:Node[T],var previous:Node[T]){

   }

  var first:Node[T]=null
  var last:Node[T]=null
  var size0=0

  /**
    * 大小
    *
    * @return
    */
  override def size(): Int = size0

  /**
    * 是否为空
    *
    * @return
    */
  override def isEmpty(): Boolean = size0==0

  /**
    * 添加
    * O(n)
    * @param ele
    */
  override def add(ele: T): Unit = {
    val newNode=new Node(ele,null,null)
    if(last!=null){
      newNode.previous=last
      last.next=newNode
      last=newNode
    }else{
      first=newNode
      last=newNode
    }
    size0+=1
  }

  override def add(ele: T, index: Int): Unit = {
    rangeCheckForAdd(index)
//    val eleNode=Node[T](ele,null,null)
    if(index==0){
      val eleNode=new Node[T](ele,first,null)
      first=eleNode
    }else{
      val previousNode = findNode(index-1)
      val nextNode=previousNode.next
      val eleNode=new Node[T](ele,nextNode,previousNode)
      previousNode.next=eleNode
      if(previousNode==last){
        last=eleNode
      }else{
        nextNode.previous=eleNode
      }
    }
    size0+=1
  }


  override def set(ele: T, index: Int): T = {
    rangeCheck(index)
    val currentN=findNode(index)
    val oldEle=currentN.ele
    currentN.ele=ele
    oldEle
  }

  def findNode(index:Int):Node[T]={
    var currentNode:Node[T]=null
    if(index <= (size0>>2)){
      currentNode=new Node[T](null.asInstanceOf[T],first,null)
      for(_ <- (0 to index)){
        currentNode=currentNode.next
      }
    }else{
      currentNode=new Node[T](null.asInstanceOf[T],null,last)
      for (_ <- (size0-1 to index by -1)){
        currentNode=currentNode.previous
      }
    }
    currentNode
  }

  override def delete(index: Int): T = {
    rangeCheck(index)
    var currentNode:Node[T]=null
    if(index==0){
      first=first.next
    }else{
      currentNode=findNode(index)
      currentNode.previous.next=currentNode.next
      if(currentNode==last){
        last=currentNode.previous
      }else{
        currentNode.next.previous=currentNode.previous
      }
    }
    size0-=1
    currentNode.ele
  }

  override def get(index: Int): T = {
    rangeCheck(index)
    findNode(index).ele
  }

  override def clear(): Unit = {
    last=null
    size0=0
  }

  def rangeCheck(index: Int): Unit = {
    if (index < 0 || index >= size0) {
      throw new IndexOutOfBoundsException("index out of bound !!!")
    }
  }

  def rangeCheckForAdd(index: Int): Unit = {
    if (index < 0 || index > size0) {
      throw new IndexOutOfBoundsException("index out of bound !!!")
    }
  }

  override def toString(): String = {

    val sb=new StringBuilder()
    var lastN=first
    for(_ <- (0 until size0))  {
      sb.append(s"${lastN.ele}\n")
      lastN=lastN.next
    }

    sb.toString()
  }

}

object LinkedListViaDouble{

  def apply[T](): LinkedListViaDouble[T] = new LinkedListViaDouble()

  def main(args: Array[String]): Unit = {
    val unit = LinkedListViaDouble[Int]()
    unit.add(123)
    unit.add(456)
    unit.add(789)
    unit.add(111213)
//    unit.delete(3)
    unit.add(789,4)
    println(unit)
  }

}